package com.my.leetcode;

import java.util.*;

/**
 * @author zlx
 * @desc 基于BFS进行解题
 * @date 2020-04-20
 * @param
 * @return
 **/
public class BFSProblems {


    public static void main(String[] args) {

        BFSProblems bfsProblems = new BFSProblems();

       /* int [][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        int [][] grid2 = {{2,1,1},{0,1,1},{1,0,1}};
        int [][] grid3 = {{0,1}};
        int [][] grid4 = {{1,2,1,1,2,1,1}};

        System.out.println(bfsProblems.orangesRotting(grid));
        System.out.println(bfsProblems.orangesRotting(grid2));
        System.out.println(bfsProblems.orangesRotting(grid3));
        System.out.println(bfsProblems.orangesRotting(grid4));*/

       TreeNode node1 = new TreeNode(1);
       TreeNode node2 = new TreeNode(2);
       TreeNode node3 = new TreeNode(3);
       TreeNode node4 = new TreeNode(4);

       node2.left = node1;
       node2.right = node3;

        //System.out.println(bfsProblems.findBottomLeftValue(node2));


        int [][] image = {{1,1,1},{1,1,0}, {1,0,1}};
//        int [][] res = bfsProblems.floodFill(image, 1,1, 2);
//        for(int i = 0; i< res.length;i++){
//            System.out.println(Arrays.toString(res[i]));
//        }


       /* char [][] board = {{'E','E','E','E','E'},{'E','E','M','E','E'},{'E','E','E','E','E'},{'E','E','E','E','E'}};
        char [][] res = bfsProblems.updateBoard(board, new int[]{3,0});
        for(int i = 0;i < res.length;i++){
            System.out.println(Arrays.toString(res[i]));
        }*/


        String beginWrod = "hit", endWord = "cog";
        List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
        System.out.println(bfsProblems.ladderLength(beginWrod, endWord, wordList));


    }


    /**
     * @author zlx
     * @Description 127. 单词接龙
     * 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
     *
     * 每次转换只能改变一个字母。
     * 转换过程中的中间单词必须是字典中的单词。
     * 说明:
     *
     * 如果不存在这样的转换序列，返回 0。
     * 所有单词具有相同的长度。
     * 所有单词只由小写字母组成。
     * 字典中不存在重复的单词。
     * 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
     * 示例 1:
     *
     * 输入:
     * beginWord = "hit",
     * endWord = "cog",
     * wordList = ["hot","dot","dog","lot","log","cog"]
     *
     * 输出: 5
     *
     * 解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     *      返回它的长度 5。
     * 示例 2:
     *
     * 输入:
     * beginWord = "hit"
     * endWord = "cog"
     * wordList = ["hot","dot","dog","lot","log"]
     *
     * 输出: 0
     *
     * 解释: endWord "cog" 不在字典中，所以无法进行转换。
     *
     * 解题思路： 基于广度优先搜索算法+图理论进行求解
     * @Date 2020-11-05
     * @Param [beginWord, endWord, wordList]
     * @return int
     **/
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        if(!wordList.contains(endWord)){
            return 0;
        }

        for(String word : wordList){
            addEdge(word);
        }

        addEdge(beginWord);
        int [] dis = new int[wordNumIndex];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord);
        int endId = wordId.get(endWord);
        dis[beginId] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(beginId);
        while (!queue.isEmpty()){

            int id = queue.poll();
            if(id == endId){
                return dis[id]/2 + 1;
            }

            for(int idx :edges.get(id)){

                if(dis[idx] == Integer.MAX_VALUE){
                    dis[idx] = dis[id] + 1;
                    queue.offer(idx);
                }
            }
        }
        return 0;
    }

    public Map<String, Integer> wordId = new HashMap<>();

    public List<List<Integer>> edges = new ArrayList<>();

    public Integer wordNumIndex = 0;

    //增加节点间的关系
    public void addEdge(String word){

        addWord(word);
        char [] array = word.toCharArray();
        int idA = wordId.get(word);
        for(int i = 0;i < array.length;i++){
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int idB = wordId.get(newWord);
            edges.get(idB).add(idA);
            edges.get(idA).add(idB);
            array[i] = tmp;
        }
    }

    //节点编号
    public void addWord(String word){

        if(!wordId.containsKey(word)){
            wordId.put(word, wordNumIndex++);
            edges.add(new ArrayList<>());
        }
    }


    /**
     * @author zlx
     * @Description 529. 扫雷游戏
     * 让我们一起来玩扫雷游戏！
     *
     * 给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
     *
     * 现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
     *
     * 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
     * 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。
     * 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
     * 如果在此次点击中，若无更多方块可被揭露，则返回面板。
     *
     *
     * 示例 1：
     *
     * 输入:
     *
     * [['E', 'E', 'E', 'E', 'E'],
     *  ['E', 'E', 'M', 'E', 'E'],
     *  ['E', 'E', 'E', 'E', 'E'],
     *  ['E', 'E', 'E', 'E', 'E']]
     *
     * Click : [3,0]
     *
     * 输出:
     *
     * [['B', '1', 'E', '1', 'B'],
     *  ['B', '1', 'M', '1', 'B'],
     *  ['B', '1', '1', '1', 'B'],
     *  ['B', 'B', 'B', 'B', 'B']]
     *
     * 解释:
     *
     * 示例 2：
     *
     * 输入:
     *
     * [['B', '1', 'E', '1', 'B'],
     *  ['B', '1', 'M', '1', 'B'],
     *  ['B', '1', '1', '1', 'B'],
     *  ['B', 'B', 'B', 'B', 'B']]
     *
     * Click : [1,2]
     *
     * 输出:
     *
     * [['B', '1', 'E', '1', 'B'],
     *  ['B', '1', 'X', '1', 'B'],
     *  ['B', '1', '1', '1', 'B'],
     *  ['B', 'B', 'B', 'B', 'B']]
     * @Date 2020-08-20
     * @Param [board, click]
     * @return char[][]
     **/
    public char[][] updateBoard(char[][] board, int[] click) {

        if(board == null || board[0].length <=0){
            return board;
        }
        int m = board.length;
        int n = board[0].length;
        
        boolean[][] flag = new boolean[m][n];
        int [][] directions = {{0,1}, {1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
        int [] tmp = null;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(click);
        while (!queue.isEmpty()){
            tmp = queue.poll();
             int x = tmp[0];
             int y = tmp[1];
             if(x >= 0 && x < m && y >= 0 && y < n){
                 if(!flag[x][y] && board[x][y] == 'M'){
                     board[x][y] = 'X';
                     return board;
                 }
                 System.out.println("-----x:" + x + "  y:" + y + " ----" + board[x][y]);
                 if(!flag[x][y] && (board[x][y] == 'E' || board[x][y] == 'B')){
                     int bomb = getBoard(board, directions, x, y, queue);
                     if(bomb != 0){
                         System.out.println(bomb);
                         board[x][y] = Character.forDigit(bomb, 10);
                     }else{
                         board[x][y] = 'B';
                     }
                 }

                 flag[x][y] = true;
             }

        }
        return board;
    }

    public int getBoard(char [][] board, int [][] directions, int x, int y, Queue<int[]> queue){

        Queue<int[]> tmpQueue = new LinkedList<>();
        int bomb = 0;
        for(int i =0;i < 8;i++){
            int tmpX = x + directions[i][0];
            int tmpY = y + directions[i][1];
            if(tmpX >= 0 && tmpX < board.length && tmpY >= 0 && tmpY < board[0].length){
                tmpQueue.add(new int[]{tmpX, tmpY});
                if(board[tmpX][tmpY] == 'M'){
                    bomb ++;
                }
            }
        }
        if(bomb == 0) {
            queue.addAll(tmpQueue);
        }

        return bomb;
    }







    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {

        int val = image[sr][sc];
        int [][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        boolean [][] flag = new boolean[image.length][image[0].length];
        Queue<int []> queue = new LinkedList();
        queue.add(new int[] {sr, sc});
        flag[sr][sc] = true;
        image[sr][sc] = newColor;
        while (!queue.isEmpty()){

            int [] tmp = queue.poll();
            for(int i = 0;i < 4;i++){

                int tmpX = tmp[0] + directions[i][0];
                int tmpY = tmp[1] + directions[i][1];
                if(tmpX < 0 || tmpX >= image.length || tmpY < 0 || tmpY >= image[0].length){
                    continue;
                }
                if(image[tmpX][tmpY] == val){
                    image[tmpX][tmpY] = newColor;
                    if(!flag[tmpX][tmpY]){
                        queue.add(new int[] {tmpX, tmpY});
                    }
                    flag[tmpX][tmpY] = true;
                }
            }
        }
        return image;
    }


    /**
     * @author zlx
     * @Description 513. 找树左下角的值  middle
     * 给定一个二叉树，在树的最后一行找到最左边的值。
     *
     * 示例 1:
     *
     * 输入:
     *
     *     2
     *    / \
     *   1   3
     *
     * 输出:
     * 1
     *
     *
     * 示例 2:
     *
     * 输入:
     *
     *         1
     *        / \
     *       2   3
     *      /   / \
     *     4   5   6
     *        /
     *       7
     *
     * 输出:
     * 7
     *
     *
     * 注意: 您可以假设树（即给定的根节点）不为 NULL。
     *
     * 解题思路一： 基于BFS，保存每一层第一个最左的数据
     * 解题思路二： 基于BFS，从右到左遍历，最后一个值即为最左值
     * @Date 2020-08-14
     * @Param [root]
     * @return int
     **/
    public int findBottomLeftValue(TreeNode root) {

        int val = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){

            int size = queue.size();
           // height ++;
            boolean first = false;
            for(int i = 0;i < size;i++){
                TreeNode tmp = queue.poll();
                if(tmp.left == null && tmp.right == null && !first){
                    val = tmp.val;
                    first = true;
                }

                if(tmp.left != null){
                    queue.add(tmp.left);
                }

                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
        }
        return val;

    }




    /**
     * @author zlx
     * @Description
     * @Date 2020-08-13
     * @Param [grid]
     * @return int
     **/
    public int orangesRotting(int[][] grid) {

        Queue<Direction> queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;

        int[][] directions = {{0, 1}, {1,0}, {0, -1}, {-1, 0}};
        int steps = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid[i][j] == 2){
                    queue.add(new Direction(i,j));
                }
            }
        }

        while (!queue.isEmpty()){
            int size = queue.size();
            int count = 0;
            for(int z = 0;z < size;z++) {
                Direction direction = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int tmpI = direction.x + directions[i][0];
                    int tmpJ = direction.y + directions[i][1];
                    if (tmpI < 0 || tmpI >= m || tmpJ < 0 || tmpJ >= n) {
                        continue;
                    }
                    if (grid[tmpI][tmpJ] == 1) {
                        grid[tmpI][tmpJ] = 2;
                        queue.add(new Direction(tmpI, tmpJ));
                        count++;
                    }
                }
            }
            if(count != 0){
                steps ++;
            }

        }
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid[i][j] == 1){
                    return -1;
                }
            }
        }

        return steps;
    }


    public class Direction{

        private int x;
        private int y;

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public Direction(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }





    /**
     * @author zlx
     *  199. 二叉树的右视图
     *  medium
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * 示例:
     *
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1, 3, 4]
     * 解释:
     *
     *    1            <---
     *  /   \
     * 2     3         <---
     *  \     \
     *   5     4       <---
     * @date 2020-04-22
     * @param
     * @return java.util.List<java.lang.Integer>
     **/
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        while (!queue.isEmpty()){
            int count = queue.size();
            int start = 0;
            while (start < count){

                TreeNode tmp = queue.poll();
                if(tmp.left != null){
                    queue.add(tmp.left);
                }

                if(tmp.right != null){
                    queue.add(tmp.right);
                }
                start ++;
                if(start == count){
                    res.add(tmp.val);
                }
            }

        }
        return res;
    }


    /**
     *637. 二叉树的层平均值
     * easy
     * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
     *
     * 示例 1:
     *
     * 输入:
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 输出: [3, 14.5, 11]
     * 解释:
     * 第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
     *注意：
     *
     * 节点值的范围在32位有符号整数范围内。
     * 解题思路： 基于Queue进行求解
     **/
    public List<Double> averageOfLevels(TreeNode root) {

        List<Double> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            double tmpSum = 0.0;
            int count = queue.size();
            for(int i = 0;i < count;i++){
                TreeNode treeNode = queue.poll();
                tmpSum += treeNode.val;
                if(treeNode.left != null){
                    queue.add(treeNode.left);
                }
                if(treeNode.right != null){
                    queue.add(treeNode.right);
                }
            }
            res.add(tmpSum / (count * 1.0));
        }
        return res;
    }

    /**
     *
     *107. 二叉树的层次遍历 II
     * easy
     * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     *
     * 例如：
     * 给定二叉树 [3,9,20,null,null,15,7],
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其自底向上的层次遍历为：
     *
     * [
     *   [15,7],
     *   [9,20],
     *   [3]
     * ]
     *
     * 解题思路： 基于Queue进行求解
     **/
     public List<List<Integer>> levelOrderBottom(TreeNode root) {

         List<List<Integer>> res = new ArrayList<>();
         if(root == null){
             return res;
         }
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
         while (!queue.isEmpty()){
             List<Integer> tmp = new ArrayList<>();
             int count = queue.size();
             for(int i = 0;i < count;i++){
                 TreeNode treeNode = queue.poll();
                 tmp.add(treeNode.val);
                 if(treeNode.left != null){
                     queue.add(treeNode.left);
                 }
                 if(treeNode.right != null){
                     queue.add(treeNode.right);
                 }
             }
             res.add(0, tmp);
         }
         return res;
    }

}
